'''
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，s1 的排列之一是 s2 的 子串 。

 

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
import collections
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        needs, window = collections.defaultdict(int), collections.defaultdict(int)
        left, right = 0, 0
        valid = 0
        for i in s1:
            needs[i] += 1

        while right < len(s2):
            c = s2[right]
            right += 1
            if c in needs:
                window[c] += 1
                if window[c] == needs[c]:
                    valid += 1
            while right - left >= len(s1):
                if valid == len(needs):
                    return True
                d = s2[left]
                left += 1
                if d in needs:
                    if window[d] == needs[d]:
                        valid -= 1
                    window[d] -= 1
        return False

s1 = "hello"
s2 = "ooolleoooleh"
Solution().checkInclusion(s1,s2)